Advent of Code 2020: Day 13

This day is interesting as it is relatively simple, as long as you keep your modulus arithmetic in check. Today is about busses! We are given a series of Bus IDs, which also correspond to their departure intervals from the station we are standing at. For example, the bus with ID 5 departs at 0, 5, 10, 15, ... minutes. We also get our own time of arrival to the station:

939                     (Time of arrival to station)
7,13,x,x,59,x,31,19     (Station IDs)

For now, the x’s mean nothing and should be ignored.

Part 1

We are tasked with figuring out which bus arrives first after our arrival at the bus stop. That means, we must find the bus ID, which has a departure time closest to, but not smaller, than the arrival time 939 minutes. To find this, I simply divide the arrival time with the bus ID and round up (ceil) and multiply again (see line 10 in the code below). The answer is actually the ID of this bus multiplied with the waiting time from arrival to departure so it requires a bit more than one line. The first part of the code below is simply reading the input and separating arrival time and Bus IDs. The variable ins is simply all the IDs without the x’s.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

import numpy as np

with open("input/day13.txt") as file:
    depature, lines, _ = file.read().split('\n')
    depature = int(depature)
    lines = np.array(lines.split(','))
    ins = np.array([int(b) for b in lines if b != "x"])

def part1(dep, ins):
    deps_near = np.ceil(dep / ins) * ins
    dep_near = np.min(deps_near)
    return ins[np.argmin(deps_near)] * (dep_near - dep)

Part 2

This is getting a bit more complex… In part 2, the input is interpreted differently. We are tasked with finding a point in time where the busses depart exactly in the subsequent order listed in the input with no delay in between. Given the input from before 7,13,x,x,59,x,31,19 indicates that we must find a point in time $t$ where:

1. At minute $t$ bus 7 must depart
2. At minute $t+1$ bus 13 must depart
3. At minutes $t+2 t+3$ there are no requirements (x’s)
4. At minute $t+4$ bus 59 must depart
5. At minute $t+5$ there are no requirements
6. At minute $t+6$ bus 31 must depart

Let’s play around with the math first. A bus with ID $b$ departs at time $t$ if $t \text{ mod } b = 0$. We denote $t_7$ a point in time at which bus 7 departs. We denote $t_{7,13}$ a time when bus 7 departs and bus 13 departs one minute after. We denote $t_{7,13,x,x,59}$ a time when bus 7 departs, followed by bus 13, followed by 2 minutes passing and bus 59 departing. This notation is further expanded to the whole input. We realize that at $t_{7,13,x,x,59,x,31,19}$ must also occur $t_{7,13,x,x,59,x,31}, t_{7,13,x,x,59}$ and $t_{7,13}$. Furthermore, at $t_{7,13,x,x,59,x,31}$ must also occur $t_{7,13,x,x,59}$ and $t_{7,13}$. As such, if we figure out when $t=t_{7,13}$ occurs, we limit $t$. By searching this limited $t$ we may find $t_{7,13,x,x,59}$ and limit $t$ further and so on until we find the final time. This limits the amount of time points we have to search much much smaller and actually makes the problem feasible. $t_{7,13}$ is not hard to find manually. Iterating $t = 7x$ for some increasing integer $x$ while checking for $(t + 1)\text{ mod } 13 = 0$ shows that the first $t_{7,13}$ occurs at $t=77$ . Below is table detailing when it happens, where D denotes a departure.

Now, how long does it take before this scenario $t_{7,13}$ occurs again? Well, bus 7 only departs every 7 minutes and bus 13, which departs one minute later, only departs every 13 minutes, so the next $t_{7,13}$ is at least $13 + 1$ minutes in the future. Looking at $t=77+13+1 = 91$ we see that:

This is sort of like $t=0$ since bus 7 and bus 13 departs at the same time. That is, their relative offset has reset back to zero. Hence we would expect $t_{7,13}$ to occur again exactly as far from 91 as it did from 0, meaning it will occur again at $t=91 + 77 = 168$:

Hence $t_{7,13} = 77 + 91x$ for some integer $x$. This value $91$ might seem arbitrary, but it is actually the least common multiple of $7$ and $13$, which is simply their product as they are both prime numbers.¹ Now by iterating $t = 77 + 91x$ we can check for $(t+4) \text{ mod } 59 = 0$ and find when the first $t_{7,13,x,x,59}$ occurs:

Just like before we expect to find the next $t_{7,13,x,x,59}$ at $350$ plus the least common multiple of $7, 13, 59$ which is $\text{lcm}(7,13,59) = 7 \cdot 13 \cdot 59 = 5369$ i.e. $t_{7,13,x,x,59} = 350 + 5369x$.

At $x = 1$ we have:

This may be repeated until the first $t_{7,13,x,x,59,x,31,19}$ is found thereby acquiring the algorithm:

1. Start at time $t=0$ and interval of length $i=1$
2. Select the next bus $b$
3. If the next time (explained just below) modulus $b$ is 0:
   1. Add the bus ID to the interval, $i = i + b$
   2. Go to step 2
4. If not
   1. Do $t = t + i$ and start again at step 3

The next time where a bus should arrive is called the offset. For bus 7 the offset is 0, as it should arrive at $t + 0$. For bus 13 it is 1, for bus 59 it is 4 and so on.

1

 offsets = [0,1,4,6,7]

These may be generated in python like so using numpy:

1
2
3
4

>> import numpy as np
>> lines = np.array([7,13,"x","x",59,"x",31,19])
>> np.argwhere(lines != "x")
array([[0],[1],[4],[6],[7]], dtype=int64)

This leaves us with the final algorithm programmed as so:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def part2(ins):
    offsets = np.argwhere(lines != "x")
    interval = np.int64(1)
    t = np.int64(0)
    for offset, bus in zip(offsets, ins):
        while True:
            if (t + offset) % bus == 0:
                interval *= bus
                break
            t += interval
    return t

Remark that t is made a 64 byte integer, as the default Python integer overflowed due to the size of the number.

The full code for this day can be found here. The entire repository is available at GitHub.